package buaa.leetcode.Array;

public class FindMinimumInRotatedSortedArray {
	public static int findMin(int[] num) {
        if(num.length == 0){
        	return 0;
        }
        if(num.length == 1){
        	return num[0];
        }
        if(num.length == 2){
        	return (num[0] > num[1]) ? num[1] : num[0];
        }
		return findMin(num,0,num.length-1);
    }
	public static int findMin(int[] num,int left ,int right) {
		if(left == right){
			return num[left];
		}if((right - left) == 1){
			return (num[right] > num[left]) ? num[left] : num[right];
		}else{
			int center = (left + right)/2;
			int centerMin = num[center];
			int leftMin;
			int rightMin;
			if(center-1 >= left){
				if(num[left] <= num[center-1]){
					leftMin = num[left];
				}else{
					leftMin = findMin(num,left,center-1); 
				}
			}else{
				leftMin = num[left];
			}
			if(center+1 <= right){
				if(num[center+1] <= num[right]){
					rightMin = num[center+1];
				}else{
					rightMin = findMin(num,center+1,right);
				}
			}else{
				rightMin = num[center+1];
			}
			if(rightMin < leftMin){
				return (rightMin<centerMin)?rightMin:centerMin;
			}else{
				return (leftMin<centerMin)?leftMin:centerMin;
			}
		}
	}
	public static void main(String[] args){
		int[] num = new int[]{4 ,5 ,6 ,7 ,0 ,1, 2};
		System.out.println(findMin(num));
	}
}
